
#include"Stack.h"
#include<malloc.h>
#include <NTL/ZZ.h>


void swap( ZZ * a, ZZ * b){

	ZZ k = *a;
	*a = *b;
	*b = k;
}

//partition the array so that the pivot is at its correct position
int partition(int start, int end, ZZ* arr1, ZZ* arr2){


	//declare a counter just before the start of array
	int i = start-1;
	int j = start;

	for(;j < end;j++){
		if( arr1[j] <= arr1[end]){
			i++;
			swap(arr1 +i,arr1+j);
			swap(arr2 +i,arr2+j);
		}
	}
	i++;
	swap(arr1 + i,arr1 + end);
	swap(arr2 + i,arr2 + end);
	return i;
}




struct bounds{
	int lower;
	int upper;
};

typedef struct bounds * PTRBounds;

PTRBounds getNodeBound(int lower,int upper){

	PTRBounds b = (PTRBounds)malloc(sizeof(struct bounds));

	b->lower = lower;
	b->upper = upper;

	return b;
}

void QuickSortIterative(int start,int end,ZZ * arr1, ZZ * arr2){

	PTRBounds b = getNodeBound(0,end);
	PTRBounds temp = NULL;
	STACKPTR stack = NULL;

	pushStack(&stack,b);
	int q = -1;
	while(!isEmptyStack(stack)){
//		b = popStack(&stack);
		//when this conditon is false, it simulates the return statement of recursive method
		while(b->lower < b->upper){
			q = partition(b->lower,b->upper,arr1,arr2);
			//check for larger array and store the bounds in the stack
			if(q - start > end - q){
				//store the larger bound in stack
				temp = getNodeBound(start,q-1);
				//change the current bound to the other partioned array
				b->lower = q+1;
			}else{
				//store the larger bound in stack
				temp = getNodeBound(q+1,end);
				//change the current bound to the other partioned array
				b->upper = q-1;
			}
			pushStack(&stack,b);
		}
	}
}